import java.util.HashMap;
import java.util.Map;

/**
 * 
 */

/**
 * @author zhongfang
 *
 */
public class AddToSum {

	public static int[] addSum1(int nums[], int target) {
		int[] res = { -1, -1 };
		if (nums == null) {
			return res;
		}
		HashMap<Integer, Integer> freq = new HashMap<>();
		boolean needFindHalf = (target % 2 == 0);
		int firstHalfIndex = -1;
		for (int i = 0; i < nums.length; i++) {
			if (needFindHalf && nums[i] == target / 2) {
				if (firstHalfIndex != -1) {
					res[0] = firstHalfIndex;
					res[1] = i;
					return res;
				} else {
					firstHalfIndex = i;
				}
			} else {
				freq.put(nums[i], i);
			}

		}
		for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
			// if (needFindHalf && entry.getKey() == target / 2)
			// {//由于上面放入freq的时候，就没有放入偶数target的一半值，所以可以不用处理
			// continue;
			// }
			if (freq.containsKey(target - entry.getKey())) {
				res[0] = entry.getValue();
				res[1] = freq.get(target - entry.getKey());
				return res;
			}
		}
		return res;
	}

	/**
	 * 暴力解法
	 * 
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] addSum2(int nums[], int target) {
		if (nums == null) {
			return new int[] { -1, -1 };

		}
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					return new int[] { i, j };
				}
			}
		}
		return new int[] { -1, -1 };
	}

	/**
	 * 
	 * @param nums
	 *            输入的数组已经排好序
	 * @param target
	 *            指定的和
	 * @return
	 */
	public static int[] addSum3(int nums[], int target) {
		if (nums == null) {
			return new int[] { -1, -1 };
		}
		int i = 0, j = nums.length - 1;
		while (i < j) {
			int sum = nums[i] + nums[j];
			if (sum == target) {
				return new int[] { i, j };
			} else if (sum < target) {
				i++;
			} else {
				j--;
			}
		}
		return new int[] { -1, -1 };
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums = null;
		int target = 5;
		int[] res = addSum1(nums, target);
		System.out.println(res[0]);
		System.out.println(res[1]);
	}

}
